1. Technical Field
This invention relates to the field of computer speech recognition and more particularly to a method and system for generating a minimal set of test phrases for testing a natural commands grammar.
2. Description of the Related Art
Speech recognition, also referred to as speech-to-text, is the technology that enables a computer to transcribe spoken words into computer recognized text equivalents. In practice, speech recognition has been employed in spoken command recognition and dictation. Spoken command recognition finds its greatest utility when incorporated in computer game applications, multimedia titles, and application navigation programs. Spoken command recognition can support the recognition of single words or short phrases spoken with continuous speech, such as "Open File". In contrast, the dictation function is most evident in word processing and document generation applications.
During the past decade there has been significant progress in the development of speech recognition systems. In consequence of technical advances in speech modeling techniques and recognition search strategies combined with the increased processing power of workstations and personal computers, large vocabulary continuous speech recognition is now feasible. In conjunction with advances in Natural Language Understanding (NLU), these new technical capabilities have made possible the incorporation of more natural styles of human-computer verbal interactions.
NLU technology represents the next generation of speech technology to come to market. Specifically, NLU technology permits a computer to understand the meaning of spoken or typed words. Moreover, NLU can render possible a computer's understanding of a query or statement put forth in natural human language. Simply put, using NLU technology a computer can understand not merely spoken words, but the meaning behind each spoken word. Software applications that seek to exploit this technology include expert systems, applications having user "wizards", database access systems for problem resolution, database search engines including the Internet, and combined query and response systems.
Related to NLU technology, natural command grammars bridge the gap between the simple command grammar and the NLU technology of the future. Natural command grammars, to some extent, represent the middle ground between the simple command grammar and NLU. Specifically, the natural command grammar is a finite state grammar that allows NLU-like flexibility in the number of allowable expressions per function. Presently, the nature of continuous speech recognizers necessitates a grammar's specification of every possible utterance potentially provided to the application. Significantly, the constraints on word choice imposed by these grammars can reduce perplexity and, accordingly, can lower the recognition error rate.
Although there are a number of approaches to structuring a natural commands grammar, the recognizer grammar commonly specified using Backus-Naur Form (BNF) seems most logical and has become widely used. The structure of the BNF grammar has comments, a root node branching out to sentence set nodes, sentence set nodes that branch out to sentences, or natural commands, variables in sentences that connect to phrase nodes, and a translation rule at the end of each line of grammar. It is the translation rule that translates the natural command into a functional statement which can be used by a back-end program to execute the program's functions without requiring a separate parsing program.
While simple grammars are relatively easy to develop and test, more complex grammars, including NLU and natural command grammars, are very difficult to develop and test comprehensively. For natural command grammars, the number of valid commands is for all practical purposes infinite, precluding exhaustive testing. Hence, testing every possible phrase in a natural commands grammar to verify correct interpretation by a translation rule interpreter, or other parsing technique, can be extraordinarily difficult and extremely inefficient. Current methods provide only for manual testing of each translation rule. Moreover, manual testing has proven error prone and time consuming. No present method can automatically create a minimum set of test sentences.